package Project.BothList;

import javax.management.relation.RoleInfoNotFoundException;

class Node { // 创建双向不循环的链表的类
    public  int data;   // 存放的数值
    public  Node prev;  // 前驱节点
    public  Node next;  // 后继节点

    public Node(int data) { // 构造方法，赋值数值，创建节点
        this.data = data;
        this.next = null;
        this.prev = null;
    }
}


public class MyLinkedList {
    private Node head = null;  // 标记双向链表的头节点
    private Node tail = null;  // 标记双向链表的尾节点



    /*头插法
    1.只有一个节点，头节点head,直接把创建的节点赋值过去
    2.存在多个节点
    * */
    public void addFirst(int data) {
        Node node = new Node(data);  // 通过双向链表的构造方法，创建节点
        Node cur = this.head;        // 拷贝头节点，代替移动

        if(null == this.head) {
            // 只有一个节点
            this.head = node;  // 头尾都是自身
            this.tail = node;
        } else {               // 注意 else 不可以省略，非要省略的话，需要在 head == null 的时候，return 停止程序继续向下执行
            cur.prev = node;
            node.next = head;
            head = node;
        }

    }



    // 遍历打印双向循环链表
    public void disPlay() {
        Node cur = this.head;   // 拷贝头节点，代替头节点移动

        while(null != cur) {
            System.out.print(cur.data+" ");
            cur = cur.next;
        }
        System.out.println();
    }



    /*尾插法
    1.只有一个节点的存在，同头插法只有一个节点，一样处理
    2.多个节点的存在
    * */
    public void addList(int data) {
        Node node = new Node(data);     // 通过双向链表的构造方法，创建节点
        Node cur = this.head;           // 拷贝头节点，代替头节点的移动

        if(null == cur) {
            this.head = node;
            this.tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }



//     判断数值 key 是否存在与该链表当中循环遍历
    public boolean contain(int key) {
        Node cur = this.head;      // 拷贝头节点，代替头节点的移动

        while(null != cur) {       // 注意是 cur 不等于 null,不是 cur.next ，
            if(key == cur.data) {  // cur.next == null其后继为空了，但是它本身的数值是存在的
                return true;       // 存在，找到，返回 true;
            }
            cur = cur.next;
        }
        return false;              // 双向链表遍历完，还没有找到，不存在，返回 false
    }



    // 计算该双向链表中存在多少个数值
    public int size() {
        Node cur = this.head;      // 拷贝头节点，代替头节点的移动
        int count = 0;

        while(null != cur) {       // 注意是 cur 不为空，不是 cur.next 因为 next == null其数值需要拿出来的，
            cur = cur.next;        // cur.next == null,不代表没有数值，
            count++;
        }
        return count;
    }



    /*在序号为 index 的位置之前插入数值节点
    1.判断该 index 的序号是否合理
    2.找出该 index 序号的地址
    3.插入数值节点，序号为 0 头插法，复用头插法； 序号在 尾节点位置，复用 尾插法
    * */

    // 内部判断该序号 index
    private boolean checkIndex(int index) {
        if(0 > index || index > size()) {
            return false;
        }
        return true;
    }

    // 内部查找该序号 index 的节点的地址
    private Node searchIndex(int index) {
        Node cur = this.head;                  // 头节点拷贝，代替头节点的移动

        if(null == this.head) {
            throw new RuntimeException("\"链表为空不用找了\"");
        }

        if(checkIndex(index)) {
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur;                  // 返回该序号的节点的地址
        }
        return null;                     // 该序号不合理，返回 null
    }

    public void addIndex(int index, int data) {
        Node cur = searchIndex(index);

        if(null == cur) {   // 该index 序号不合法
            return;
        }
        if(cur == this.head) {      // 等于头节点 ，复用头插法
            addFirst(data);
            return;                  // 执行完毕，停止，防止继续执行
        }

        if(cur == tail) {          // 等于尾节点，复用尾插法
            addList(data);
            return ;                  // 执行完毕，停止。防止继续执行
        }

        // 位于中间节点的插入
        Node node = new Node(data);   // 创建该插入的数值节点
        node.next = cur;
        node.prev = cur.prev;
        cur.prev.next = node;
        cur.prev = node;

    }

       /*删除 n个 第一个数值为 key 的节点
       * 1.在头的的位置
       * 2.中间和尾部 注意尾部的特殊处理*/
    public void remove(int key,int n) {
        Node cur = this.head;         // 头节点的拷贝，代替头节点的移动
        while(null != cur) {          // 注意是 cur != null,不是 cur.next ,因为 cur.next == null,但是其，是有数值存在的
            if(key == cur.data) {     // cur == null; 才是没有数值存在的
                if(this.head == cur) {      // 位于头节点的位置
                    this.head = cur.next;
                    head.prev = null;
                } else {    // 位于中间，尾部
                    cur.prev.next = cur.next;
                    if(null != cur.next){    // 位于中间节点的处理
                        cur.next.prev = cur.prev;
                    } else {          // 位于尾节点的处理
                        tail = tail.prev;
                    }
                }
                System.out.println(key+" 删除成功");
                if(1 == n--) {      // 计数删除到规定的个数停止
                    return ;        // 只是删除一个数值为key 的节点，删除停止程序，继续执行，防止再删除
                }
            }
            cur = cur.next;     // 移动节点
        }
        System.out.println(key+" 该数值的节点不存在，删除失败");
        return;                // 链表遍历完了，还没有找到该数值的节点，该数值的节点不存在，停止执行
    }



//    删除全部 key 数值的节点,没有计数，全部删除
    public void remove(int key) {
        Node cur = this.head;         // 头节点的拷贝，代替头节点的移动
        while(null != cur) {          // 注意是 cur != null,不是 cur.next ,因为 cur.next == null,但是其，是有数值存在的
            if(key == cur.data) {     // cur == null; 才是没有数值存在的
                if(this.head == cur) {      // 位于头节点的位置
                    this.head = cur.next;
                    head.prev = null;
                } else {    // 位于中间，尾部
                    cur.prev.next = cur.next;
                    if(null != cur.next){    // 位于中间节点的处理
                        cur.next.prev = cur.prev;
                    } else {          // 位于尾节点的处理
                        tail = tail.prev;
                    }
                }
                System.out.println(key+" 删除成功");
            }
            cur = cur.next;     // 移动节点
        }
    }




/*
清空链表
java中有自动回收空间的机制(JVM虚拟机),但是有一个要求就是，不可以被引用，被其他引用了，是不可
回收该节点的空间的，
这里与单链表不同，单链表只有一个引用(后继)，所以只需要删除头节点的引用，其他节点就没有引用了，
这里是双向链表，把头节点置为了 null,还有“后继”节点对其“前驱”的引用，对于其他节点而言还有也是一样的，
有引用存在，JVM无法自动回收空间，所以需要一个一个的释放 null

* */
public void clear() {
    while(null != this.head) {  // 注意：是 head != null 不是 head.next,head.next == null 也是一个有数值的节点,
        Node cur = this.head.next;    // 拷贝 代替，防止丢失后面的节点位置
        this.head.next = null;
        this.head.prev = null;
        this.head = cur;  // 移动节点
    }
    this.tail.prev = null;   // 最后跳出循环，还有尾节点的前驱，没有置为 null
}











}
